﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Stack
{
    /// <summary>
    /// 循环数组
    /// </summary>
    /// <typeparam name="E"></typeparam>
    public class LoopQueue<E> : Queue<E>
    {
        private E[] data;
        private int front, tail;//对首对尾
        private int size;


        public LoopQueue(int capacity)
        {
            front = 0;
            tail = 0;
            tail = 0;
            data = new E[capacity + 1];
        }

        public LoopQueue() : this(10) { }



        public int getCapacity()
        {
            return data.Length - 1;
        }

        public E dequeue()
        {
            if (isEmpty())
                throw new Exception("队列为空");
            E ret = data[front];
            front = (front + 1) % data.Length;
            size--;
            if (size == getCapacity() / 4 && getCapacity() / 2 != 0)
                Resize(getCapacity() / 2);
            return ret;
        }

        public void enqueue(E e)
        {
            if ((tail + 1) % data.Length == front)
                Resize(getCapacity() * 2);
            data[tail] = e;
            tail = (tail + 1) % data.Length;
            size++;
        }

        public E getFront()
        {
            if (isEmpty())
                throw new Exception("队列为空");
            return data[front];
        }

        public int getSize()
        {
            return size;
        }

        public bool isEmpty()
        {
            return front == tail;
        }


        //自动扩容
        private void Resize(int NewCapacity)
        {
            E[] NewData = new E[NewCapacity + 1];
            for (int i = 0; i < size; i++)
                NewData[i] = data[(i + front) % data.Length];
            data = NewData;
            front = 0;
            tail = size;
        }



        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.Append(string.Format("Queue: size = {0} , capacity = {1}\n", size, getCapacity()));
            res.Append("front [");
            for (int i = front; i != tail; i = (i + 1) % data.Length)
            {
                res.Append(data[i]);
                if ((i + 1) % data.Length != tail)
                    res.Append(", ");
            }
            res.Append("] tail");
            return res.ToString();
        }


    }
}
